package com.wtgroup.demo.leetcode.q042_接雨水;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 单调栈方式
 * <p>
 * 栈底到栈顶递减
 * @author 60906
 * @date 2021/5/4 16:57
 */
public class Q042_LC_Stack {

    public int trap(int[] height) {
        int n = height.length;
        // 自底到顶递减, 放的是下标
        Deque<Integer> stack = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 比栈顶大, 说明可以接水了
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 和top前面的一个联合接水, 同时排除top的影响(top在之前作为left和别人配对接过水)
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break; // 没有可用 left 了
                }
                int left = stack.peek();
                int width = i - left - 1;
                int hght = Math.min(height[i], height[left]) - height[top];
                ans += width * hght;
            }
            // 比栈顶小, 依次 push 即可
            stack.push(i);
        }

        return ans;
    }
}
